package club.xiaojiawei.strings;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/5/22 12:26 AM
 * @question 239. 滑动窗口最大值
 * @description 给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。
 * 返回 滑动窗口中的最大值 。
 */
public class MaxSlidingWindow239 {

    public static void main(String[] args) {
        int[] nums = {8,7,6,3,5,2,1};
        int[] result = maxSlidingWindow4(nums, 3);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 暴力解法 - 超时了
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (k == 1){
            return nums;
        }
        int max = Integer.MIN_VALUE;
        int[] result = new int[nums.length < k? 1 : nums.length - k + 1];
        int l = 0;
        int r = 0;
        while (r < nums.length){
            if (nums[r] > max){
                max = nums[r];
            }
            if (r - l == k - 1){
                result[l] = max;
                if (nums[l++] == max){
                    max = nums[l];
                    r = l;
                    continue;
                }
            }
            r++;
        }
        return result;
    }

    /**
     * 官方-优先队列 PriorityQueue
     * 时间复杂度：O(nlogn)
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1]);
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
//            去除无效的最大值（即不在窗口内的最大值）
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }

    /**
     * 练习-优先队列 PriorityQueue
     * @param nums
     * @param k
     * @return
     */
    public static int[] test2(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        PriorityQueue<int[]> queue = new PriorityQueue<>((i1, i2) -> i1[0] == i2[0]? i2[1] - i1[1]: i2[0] - i1[0]);
        for (int i = 0; i < k; i++) {
            queue.add(new int[]{nums[i], i});
        }
        result[0] = queue.peek()[0];
        for (int i = k; i < nums.length; i++) {
            queue.add(new int[]{nums[i], i});
            while (queue.peek()[1] <= i - k){
                queue.poll();
            }
            result[i - k + 1] = queue.peek()[0];
        }
        return result;
    }

    /**
     * 官方-单调队列
     * 时间复杂度：O(n)
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow3(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }


    /**
     * 官方-分块+预处理(妙呀！)
     * 将一个窗口分为前后两个部分
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow4(int[] nums, int k) {
        int n = nums.length;
        int[] prefixMax = new int[n];
        int[] suffixMax = new int[n];
        for (int i = 0; i < n; ++i) {
            if (i % k == 0) {
                prefixMax[i] = nums[i];
            }
            else {
                prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
            }
        }
        for (int i = n - 1; i >= 0; --i) {
            if (i == n - 1 || (i + 1) % k == 0) {
                suffixMax[i] = nums[i];
            } else {
                suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
            }
        }

        int[] ans = new int[n - k + 1];
        for (int i = 0; i <= n - k; ++i) {
            ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);
        }
        return ans;
    }
}
